Design and Analysis of Algorithms

Course Title: Design and Analysis of Algorithms

Course No: CSC314

Nature of the Course: Theory + Lab

Semester: V

Full Marks: 60 + 20 + 20

Pass Marks: 24 + 8 + 8

Credit Hrs: 3

Course Description

This course introduces basic elements of the design and analysis of computer algorithms. Topics include asymptotic notations and analysis, divide and conquer strategy, greedy methods, dynamic programming, basic graph algorithms, NP-completeness, and approximation algorithms. For each topic, one or more representative problems and their algorithms shall be discussed.

Course Objectives
  • Analyze the asymptotic performance of algorithms.
  • Demonstrate a familiarity with major algorithm design techniques.
  • Apply important algorithmic design paradigms and methods of analysis.
  • Solve simple to moderately difficult algorithmic problems arising in applications.
  • Demonstrate the hardness of simple NP-complete problems.
Detail Syllabus
Unit 1: Foundations of Algorithm Analysis (4 Hrs.)
  • Algorithms and its properties
  • RAM model
  • Time and Space Complexity
  • Detailed Analysis of algorithms
  • Concept of Aggregate Analysis
  • Asymptotic Notations: Big-O, Big-Ω, and Big-Ө Notations
  • Recursive Algorithms
  • Recurrence Relations
  • Solving Recurrences: Recursion Tree Method, Substitution Method, Masters Theorem
Unit 2: Iterative Algorithms (4 Hrs.)
  • Basic Algorithms: GCD, Fibonacci Numbers
  • Searching Algorithms: Sequential Search
  • Sorting Algorithms: Bubble Sort, Selection Sort, Insertion Sort
Unit 3: Divide and Conquer Algorithms (8 Hrs.)
  • Concepts of Divide and Conquer
  • Binary Search, Min-Max algorithm
  • Sorting Algorithms: Merge Sort, Quick Sort, Randomized Quick Sort, Heap Sort
  • Order Statistics: Median order, Selection in Expected Linear Time, Selection in Worst Case Linear Time
Unit 4: Greedy Algorithms (6 Hrs.)
  • Introduction to Greedy Approach
  • Greedy Algorithms: Fractional Knapsack, Job Sequencing, Minimum Spanning Tree (Kruskal’s and Prim’s), Dijkstra’s Shortest Path
  • Huffman Coding
Unit 5: Dynamic Programming (8 Hrs.)
  • Introduction to Dynamic Programming
  • DP Algorithms: Matrix Chain Multiplication, String Editing, 0-1 Knapsack, Floyd-Warshall, Travelling Salesman
  • Memoization Strategy
Unit 6: Backtracking (5 Hrs.)
  • Introduction to Backtracking
  • Backtracking Algorithms: Subset Sum, Zero-One Knapsack, N-Queen Problem
Unit 7: Number Theoretic Algorithms (5 Hrs.)
  • Introduction to Number Theoretic Notation
  • Solving Modular Linear Equations: Euclid’s and Extended Euclid’s Algorithms
  • Primality Testing: Miller-Rabin Randomized Test
Unit 8: NP Completeness (5 Hrs.)
  • Tractable and Intractable Problems, Complexity Classes
  • NP Complete Problems: Concept of Cooks Theorem, Proof of NP Completeness
  • Approximation Algorithms
Laboratory Works

Students should implement algorithms and analyze their behavior in C/C++. The following algorithms should be implemented:

  • Basic iterative algorithms: GCD, Fibonacci Sequences, Sequential and Binary Search
  • Basic sorting algorithms: Bubble Sort, Selection Sort, Insertion Sort
  • Divide and Conquer: Binary Search, Merge Sort, Heap Sort, Quick Sort, Randomized Quick Sort
  • Selection Problem
  • Greedy Algorithms: Fractional Knapsack, Job Sequencing, Kruskal’s, Prim’s, Dijkstra’s Algorithm
  • Dynamic Programming Algorithms
  • Backtracking Algorithms
  • Approximation Algorithm
Recommended Books
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms”, Third Edition, MIT Press, 2009.
  • Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, “Computer Algorithms”, Second Edition, Silicon Press, 2007.
  • Kleinberg, Jon, and Eva Tardos, “Algorithm Design”, Addison-Wesley, First Edition, 2005.